第6章　抽象データ型

1. 基準

その記述は曖昧さがなく厳密でなければならない

その記述は完全でなければならない。あるいは、少なくとも、ここのケースについて期待される程度の完全さがなければならない。

その記述は過剰仕様であってはならない

2. 実装のバリエーション

1. スタックの表現

スタックの表現

ARRAY_UP

配列represetationと整数countからなり、スタックの要素は配列のインデックス1から上に向かってcountまでの位置に格納される

ARRAY_DOWN

ARRAY_UPとの違いは配列の最後から要素が格納される

LINKED

要素itemを直前にpushされた要素を含むセルへのポインタを含むpreviousからなる。

2. 過剰仕様の危険性

ソフトウェアのコストの17%以上がデータ形式の変更が伴って発生している。

操作するデータの物理的な構造に依存しない柔軟な実装が必要

3. オブジェクトを抽象的に見るには

1. 操作を使う

スタックだと一番上の要素に追加するput

スタックが空じゃない場合に一番上の要素を取り除くremove

スタックが空じゃない場合に一番上の要素が何であるかを問い合わせるitem

スタックが空であるか判定する問合せ

空のスタックを生成するmakeなどがある

code:stack

count INTEGER

2. モジュール社会のための無干渉主義

3. 名前の一貫性

4. どのように抽象を扱わないようにするのか？

4. 仕様記述を形式化する

抽象データ型（以下ADT）の仕様は以下の4つのパラグラフから構成される

TYPES

FUNCTIONS

AXIOMS

PRECONDITION

1. 型を記述する

型はオブジェクトの集合

ADTの仕様記述を満たすオブジェクトの集合に属するオブジェクトは、そのADTのインスタンスであると言える。

TYPESパラグラフは仕様記述に登場する型を列挙する

STACK[G]

2. 総称性

3. 関数を列挙する

FUNCTIONSパラグラフはADTのインスタンスに適用可能な操作をリストアップする。

STACKのFUNCTIONSパラグラフは以下の通りになる

code:Functions Paragraph

4. 関数の分類

生成関数(creator function)

他の型のインスタンスからTのインスタンスを生成する操作。

問合せ関数(query function)

他の型のインスタンスで表されたTのインスタンスの属性を取り出す操作。

コマンド関数(command function)

Tの既存のインスタンスからTの新しいインスタンスを生成する操作。

5. AXIOMS（公理）パラグラフ

関数の値を与えるのではなく、関係するすべての属性を記述する。

STACKのAXIOMSパラグラフ

code:axioms parahraph

A1 item(put(s, x)) = x

A2 remove(put(s, x)) = s

A3 empty(new)

A4 not empty(pur(s, x))

6. スタックについて知っている2、3のこと

ADTの仕様記述は暗黙的であること。

適用可能な関数というという形でオブジェクトの集合を暗黙的に定義する。

関数そのものもまた暗黙のうちに定義される。

暗黙的であることは暗に開かれていることを意味する。

7. 部分関数

Xのすべての要素について定義されていない場合、ソース集合Xからターゲット集合Yへの関数は部分関数である。

STACKのremoveやitemはスタック集合の全ての要素に適用できるわけではない

部分関数ではない関数は全関数。

8. 事前条件

部分関数を含む全てのADT仕様記述についての定義域を指定するのがPRECONDITIONSパラグラフの役割である。

code:preconditions paragraph

9. 完全な仕様記述

STACKの完全な仕様記述

code: スタックのADT仕様記述

TYPES

FUNCTIONS

AXIOMS

- item(put(s, x)) = x

- remove(put(s, x)) = s

- empty(new)

not empty(put(s, x))

PRECONDITIONS

10. 真実以外の何物でもない

抽象データ型の仕様記述力は、過剰仕様にならずにデータ構造の本質的な属性を捉えるところから得られる。

これによりデータ構造を伴う計算の一般的なモデルが得られる。

5. 抽象データ型からクラスへ

1. クラス

クラスの定義

クラスは（部分的であっても良い）実装を伴う抽象データ型である。

クラスを得るにはADTを準備し実装を決めなければならない。

実装は部分的であっても良いと書かれているので、暫定クラスと有効クラスを区別できる。

暫定クラスと有効クラスの定義

完全に実装されているクラスを有効クラス（effective class）という。部分的にしか実装されていないか、全く実装されていないクラスを暫定クラス（deferred class）という。クラスは暫定クラスか有効クラスのいずれかである。

2. 有効クラスの作成方法

E1:ADTの仕様記述

E2:表現の選択

E3:関数(E1)から表現(E2)への対応

3. 暫定クラスの役割

表現の選択と関数から表現への対応がなければならない。どれか一つが欠けてたら暫定クラスになる。

暫定クラスは分析と設計に役立つ。

オブジェクト指向分析では、実装に関する詳細は全く必要とされない。

オブジェクト指向分析では、実装の多くの側面を無視することができる。

暫定クラスから始めて有効クラスを獲得した場合、前のクラスをあとのクラスの祖先として維持し、分析および設計過程の生きた記憶として使うことができる。

4. 抽象データ型と情報隠蔽

ADTの仕様を満たすクラスなら、E1のADT仕様記述は公開するがE2とE3の表現の選択とその表現によるADT関数の実装は非公開にすべきである。

5. より命令的な見方を取り入れる

適用的な見方

スタックの要素を受け取り新しいスタックを返す操作

オブジェクトを変更できる操作

G型の引数に受け取るルーチン

新しいスタックを生成する代わりにスタックの一番上に新しい要素をプッシュしてスタックを修正する

ADTの公理

ルーチンの事後条件としてensureを定義

7. オブジェクト指向によるソフトウェア構築

オブジェクト指向によるソフトウェア構築とは、抽象データ型の（その部分的な実装も含む）構造化された集合として、ソフトウェアシステムを構築することである。

基本は抽象データ型と言う概念である。

ソフトウェアに必要なのは数学的な概念のADTそのものではなく、ソフトウェアの概念であるADTの実装である。

これらの実装は完全である必要はなく、「部分的な実装も含む」と言う修飾語によって暫定クラスが含まれる。これには、実装されている特性が一つもない完全な暫定クラスと言う極端なケースが含まれる。

システムはクラスの集合である、その中には特に責任を持つもの、すなわち、トップやメインプログラムは存在しない。

この集合は2種類のクラス間関係、すなわち、顧客と継承のおかげで構造化されている。